package com.lfg.learn.btree;

import java.util.ArrayList;
import java.util.List;

public class BPlusTree {


    private static final int MAX_ENTRY = 5;
    private static final int MIN_ENTRY = Double.valueOf(Math.ceil(MAX_ENTRY / 2.0)).intValue();

    private Node root = null;


    public static void main(String[] args) {
        BPlusTree tree = new BPlusTree();
        tree.insert(1);
        tree.insert(2);
        tree.insert(3);
        tree.insert(4);
        tree.insert(5);
        tree.insert(6);
        tree.insert(8);
        tree.insert(11);
        tree.insert(21);
        tree.insert(31);
        tree.insert(41);
        tree.insert(51);
        tree.insert(16);
        tree.insert(18);
        tree.visit(tree.root);
        System.out.println("xxx");

        tree.delete(1);
        tree.visit(tree.root);
        System.out.println("xxx");

        tree.delete(3);
        tree.visit(tree.root);
        System.out.println("xxx");
    }


    public void visit(Node node) {

        for (Node child : node.getChildren()) {
            if (child.isLeaf()) {
                System.out.print(child.getValue() + ",");
                continue;
            }
            visit((child));
        }

    }

    public Node insert(int i) {
        Node newNode = new Node();
        newNode.setValue(i);
        newNode.setLeaf(true);
        if (root == null) {
            root = newNode;
            return newNode;
        }
        Node node = root;
        while (true) {
            List<Node> children = node.getChildren();
            if (children == null || children.isEmpty() || children.get(0).isLeaf()) {
                break;
            }
            if (children.get(children.size() - 1).getValue() < newNode.getValue()) {
                node = children.get(children.size() - 1);
                continue;
            }

            for (Node entry : children) {
                if (i < entry.getValue()) {
                    break;
                }
                node = entry;
            }
        }

        insert(newNode, node);
        return newNode;
    }

    private void insert(Node newNode, Node node) {

        newNode.setParent(node);

        if (node.isLeaf()) {
            node.setChildren(new ArrayList<>(5));
            Node oldNode = new Node();
            oldNode.setValue(node.getValue());
            oldNode.setLeaf(true);
            node.getChildren().add(oldNode);
            node.getChildren().add(newNode);
            node.setLeaf(false);

            oldNode.setNext(newNode);
            newNode.setPre(oldNode);

            oldNode.setParent(node);

            return;
        }

        int index = 0;
        boolean add = false;
        for (; index < node.getChildren().size(); index++) {
            Node entry = node.getChildren().get(index);
            if (newNode.getValue() < entry.getValue()) {
                node.getChildren().add(index, newNode);

                add = true;

                Node pre = entry.getPre();
                link(newNode, pre);
                break;
            }
        }
        if (!add) {
            Node pre = node.getChildren().get(node.getChildren().size() - 1);
            node.getChildren().add(newNode);
            link(newNode, pre);
        }


        // 需要拆分
        if (node.getChildren().size() > MAX_ENTRY) {

            List<Node> children = node.getChildren();
            List<Node> list1 = new ArrayList<>(children.subList(0, MIN_ENTRY));
            List<Node> list2 = new ArrayList<>(children.subList(MIN_ENTRY, children.size()));
            Node node2 = new Node();
            node2.setChildren(list2);
            for(Node child2 : list2){
                child2.setParent(node2);
            }

            node2.setValue(list2.get(0).getValue());
            node.setChildren(list1);
            Node parent = node.getParent();
            if (parent == null) {
                root = new Node();
                root.setLeaf(false);
                root.setChildren(new ArrayList<>(5));
                root.getChildren().add(node);
                root.getChildren().add(node2);
                root.setValue(node.getValue());
                node.setParent(root);
                node2.setParent(root);
                node.setNext(node2);
                node2.setPre(node);

                return;
            }
            insert(node2, parent);
        }
    }

    private void link(Node newNode, Node pre) {
        Node oldNext = pre.getNext();
        pre.setNext(newNode);
        newNode.setNext(oldNext);
        newNode.setPre(pre);
        if (null != oldNext) {
            oldNext.setPre(newNode);
        }
    }

    public Node search(Node node, int i) {
        if (node == null) {
            return null;
        }
        Node child = null;
        if (node.isLeaf()) {
            if (node.getValue() == i) {
                return node;
            }
            return null;
        }
        for (Node entry : node.getChildren()) {
            if (i < entry.getValue()) {
                break;
            }
            child = entry;
        }
        return search(child, i);
    }


    public void delete(int i) {
        Node node = search(root, i);
        if (null == node) {
            return;
        }
        Node parent = node.getParent();
        if (parent == null) {
            root = null;
            return;
        }
        Node next = node.getNext();

        deleteNode(node, parent);
        if (node.getValue() == parent.getValue()) {
            updateValue(node, parent, next.getValue());
        }
        balance(parent);
    }

    private void deleteNode(Node node, Node parent) {
        unlink(node);
        parent.getChildren().remove(node);
    }

    private void updateValue(Node node, Node parent, int newValue) {
        while (parent != null) {
            if (node.getValue() == parent.getValue()) {
                parent.setValue(newValue);
                parent = parent.getParent();
            } else {
                return;
            }
        }
    }

    private void balance(Node parent) {
        if (root == parent) {
            if (parent.getChildren().size() == 1) {
                root = parent.getChildren().get(0);
                root.setChildren(null);
                root.setLeaf(true);
            }
            return;
        }
        if (parent.getChildren().size() > MIN_ENTRY) {
            return;
        }
        Node gParent = parent.getParent();
        Node node = parent.getChildren().get(0);
        if (gParent.getChildren().get(0) == parent) {
            Node next = gParent.getChildren().get(1).getChildren().get(0);
            if (next.getParent().getChildren().size() > MIN_ENTRY) {
                next.getParent().getChildren().remove(0);
                updateValue(next, next.getParent(), next.getNext().getValue());
                parent.getChildren().add(next);

            } else {
                parent.getChildren().addAll(next.getParent().getChildren());
                gParent.getChildren().remove(next.getParent());
                unlink(next.getParent());
                balance(gParent);

            }
        } else {
            Node pre = node.getPre();
            if (pre.getParent().getChildren().size() > MIN_ENTRY) {
                parent.getChildren().add(0, pre);
                updateValue(node, parent, pre.getValue());
            } else {
                pre.getParent().getChildren().addAll(parent.getChildren());
                gParent.getChildren().remove(parent);
                unlink(parent);
                balance(gParent);
            }
        }
    }

    private void unlink(Node parent) {
        Node pre = parent.getPre();
        Node next = parent.getNext();
        if (pre != null) {
            pre.setNext(next);
        }
        if (next != null) {
            next.setPre(pre);
        }
    }
}
